#ifndef BINARY_TREES_H
#define BINARY_TREES_H

#include <iostream>
#include <queue>

using namespace std;

struct node
{
  int data;
  struct node *left;
  struct node *right;
};

struct node* newNode(int data)
{
  node *myNode = new node();
  myNode->data = data;
  myNode->left = NULL;
  myNode->right = NULL;

  return myNode;
}

bool lookup(node *myNode, int number)
{
  node *current_node = myNode;

  while(1) 
  { 
    //cout << "current_node->data == " << number << endl;
    //cout << "number = " << number << endl;

    if(current_node->data == number)
    {
      return true;
    }

    if(current_node->data > number) 
    {
      if(current_node->left != NULL)
      {
        current_node = current_node->left;
      }
      else
      {
        return false;
      }
    }

    if(current_node->data < number)
    {
      if(current_node->right != NULL)
      {
        current_node = current_node->right;
      }
      else
      {
        return false;
      }
    }
  }
}

void insert(int number)
{
  
}

int getSize()
{
  
}

int maxDepth()
{
  
}

int minDepth()
{
  
}

void printPreOrder(node *myNode)
{
  cout << myNode->data << " ";
  if(myNode->left != NULL) printPreOrder(myNode->left);
  if(myNode->right != NULL) printPreOrder(myNode->right);
}

void printInOrder(node *myNode)
{
  if(myNode->left != NULL) printInOrder(myNode->left);
  cout << myNode->data << " ";
  if(myNode->right != NULL) printInOrder(myNode->right);
}

void printPostOrder(node *myNode)
{
  if(myNode->left != NULL) printPostOrder(myNode->left);
  if(myNode->right != NULL) printPostOrder(myNode->right);
  cout << myNode->data << " ";
}

void printBFS(node *myNode)
{
  queue<node *> node_queue;
  node_queue.push(myNode);
  while(!node_queue.empty())
  {
    if(node_queue.front()->left != NULL)
    {
      node_queue.push(node_queue.front()->left);
    }
    if(node_queue.front()->right != NULL)
    {
      node_queue.push(node_queue.front()->right);
    }
    cout << node_queue.front()->data << " ";
    node_queue.pop();
  }
}

void inorder_traverse(queue<node *> node_queue, node *myNode)
{
 if(myNode->left != NULL) inorder_traverse(node_queue, myNode->left);
 node_queue.push(myNode);
 cout << "push " << myNode->data << endl;
 if(myNode->right != NULL) inorder_traverse(node_queue, myNode->right);
}

bool isAscendant(queue<node *> node_queue)
{
  int temp = node_queue.front()->data;
  while(!node_queue.empty())
  {
    if(temp > node_queue.front()->data) return false;
    temp = node_queue.front()->data;
    node_queue.pop();
  }
  return true;
}

bool isBST(queue<node *> node_queue, node *myNode)
{
  inorder_traverse(node_queue, myNode);
  return isAscendant(node_queue);
}

#endif
